#ifndef __LINKLIST_H_
#define __LINKLIST_H_

#include <stddef.h>
#include "DynamicArray.h"

using ElementType = int;

class LinkList
{
public:
    LinkList();
    LinkList(const LinkList &list);
    LinkList &operator=(const LinkList &list);
    ~LinkList();

    // 插入
    // 尾插法
    void InsertTail(const ElementType &element);
    // 头插法
    void InsertHead(const ElementType &element);
    // 中间插
    void InsertByIndex(size_t index, const ElementType &element);

    // 删除
    // 按位置删除
    void RemoveByIndex(size_t index);
    // 按值删除
    void RemoveByElement(const ElementType &element);

    // 查找
    // 按位置查找
    ElementType *FindByIndex(size_t index); // 返回数据域 返回指针，可以判断非法
    // 按值查找
    DARRAY::DynamicArray FindByElement(const ElementType &element); // 返回数据域的指针集合

    // 修改
    // 按位置修改
    void UpdateByIndex(size_t index, const ElementType &element);
    // 按值修改
    void UpdateByElement(const ElementType &oldValue, const ElementType &newValue);

    // 排序
    void BubbleSort();
    void Sort();
    // 作业：倒数第n个元素
    ElementType *GetReserveIndex(size_t index);

    // 归并
    LinkList Merge(const LinkList &list);
    // 作业：交并补
    // 取交集
    LinkList FdIntrSctn(const LinkList &list);
    // 取并集
    LinkList FindUnionSet(const LinkList &list);
    // 取补集
    LinkList FindDifference(const LinkList &list);

    // 链表的逆序
    void Reserve();
    // 递归逆序
    void Reserve2();

    void show();

private:
    struct Node
    {
        Node(const ElementType &value) // 结构体构造函数
        {
            this->value = value; // 将传入的参数赋值给当前节点的value成员
            next = nullptr;      // 初始化节点指针
        }
        ElementType value; // 数据域：存储节点的实际数据
        Node *next;        // 指针域：指向下一个节点的地址
    };
    Node *head; // 头指针 (找到第一个节点，便可以找到整个链表)
    void FastSort(Node *start, Node *end);
    Node *reserve(Node *node);
    size_t size; // 链表中元素个数
};

#endif
